Given the root of a binary tree, collect a tree's nodes as if you were doing this:
- Collect all the leaf nodes.
- Remove all the leaf nodes.
- Repeat until the tree is empty.
Example 1:
Input: root = [1,2,3,4,5] Output: [[4,5,3],[2],[1]] Explanation: [[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
Example 2:
Input: root = [1] Output: [[1]]
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. -100 <= Node.val <= 100
Average Rating: 5.00 (9 votes)
Approach 1: DFS (Depth-First Search) with sorting
Intuition
The order in which the elements (nodes) will be collected in the final answer depends on the "height" of these nodes. The height of a node is the number of edges from the node to the deepest leaf. The nodes that are located in the ith height will be appear in the ith collection in the final answer. For any given node in the binary tree, the height is obtained by adding 1 to the maximum height of any children. Formally, for a given node of the binary tree root, it's height can be represented as
height(root)=1+max(height(root.left), height(root.right))
Where root.left and root.right are left and right children of the root respectively
Algorithm
In our first approach, we'll simply traverse the tree recursively in a depth first search manner using the function int getHeight(node), which will return the height of the given node in the binary tree. Since height of any node depends on the height of it's children node, hence we traverse the tree in a post-order manner (i.e. height of the childrens are calculated first before calculating the height of the given node). Additionally, whenever we encounter a null node, we simply return -1 as it's height.
Next, we'll store the pair (height, val) for all the nodes which will be sorted later to obtain the final answer. The sorting will be done in increasing order considering the height first and then the val. Hence we'll obtain all the pairs in the increasing order of their height in the given binary tree.
Attached below is the video which shows the calculation of height in a height-first-search manner for the binary tree given in the example.
Below is the implementaion of this approach
Complexity Analysis
-
Time Complexity: Assuming N is the total number of nodes in the binary tree, traversing the tree takes O(N) time. Sorting all the pairs based on their height takes O(NlogN) time. Hence overall time complexity of this approach is O(NlogN)
-
Space Complexity: O(NlogN), the space used by
pairsandsolution.
Approach 2: DFS (Depth-First Search) without sorting
We've seen in approach 1 that there is an additional sorting that is being performed, which increases the overall time complexity to O(NlogN). The question we can ask here is, can we do better than this? To answer this, we try to remove the sorting by directly placing all the values in their respective positions, i.e. instead of using the pairs array to collect all the (height, val) pairs and then sorting them based on their heights, we'll directly obtain the solution by placing each element (val) to its correct position in the solution array. To clarify, in the given binary tree, [4, 3, 5] goes into the first position, [2] goes into the second position and [1] goes into the third position in the solution array.
To do this, we modify our getHeight method to directly insert the node's value in the solution array at the correct location. Solution array is kept empty in the beginning and as we encounter elements with increasing height, we'll keep increasing the size of the solution array to accomodate for these elements. For example, if our solution array currently is [[4, 3, 5]] and if we want to insert 2 at the second position, we first create the space for 2 by increasing the size of the solution array by 1 and then insert 2 at it's correct location.
-
[[4, 3, 5]] -> [[4, 3, 5], []] # increase the size of solution array -
[[4, 3, 5], []] -> [[4, 3, 5], [2]] # insert 2 at it's correct location
Below is the implementation of the above mentioned approach.
Complexity Analysis
-
Time Complexity: Assuming N is the total number of nodes in the binary tree, traversing the tree takes O(N) time and storing all the pairs at the correct position also takes O(N) time. Hence overall time complexity of this approach is O(N).
-
Space Complexity: O(N), the space used by
solutionarray.
Last Edit: December 6, 2020 10:42 AM
Here's a simple python DFS implementation used to populate a dictionary (key = index, values = list of nodes), O(N) space, O(N) time, beats 99%
The DFS recursively calculates the layer index by getting the maximum depth from the left and right subtrees of a given node, which is then used to populate the dictionary.
def findLeaves(self, root: TreeNode) -> List[List[int]]:
output = collections.defaultdict(list)
def dfs(node, layer):
if not node:
return layer
left = dfs(node.left, layer)
right = dfs(node.right, layer)
layer = max(left, right)
output[layer].append(node.val)
return layer + 1
dfs(root, 0)
return output.values()
February 18, 2021 8:51 AM
is it necessary to not remove the nodes from root passed in ?
April 11, 2021 1:22 AM
Relatively concise answer:
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> leaves = new ArrayList<>();
findLeaves(root, leaves);
return leaves;
}
public int findLeaves(TreeNode n, List<List<Integer>> leaves) {
if(n == null) return 0;
int dOrder = 1+ Math.max(findLeaves(n.left, leaves), findLeaves(n.right, leaves));
if(dOrder != 0) {
if(leaves.size() == dOrder - 1) leaves.add(new ArrayList<Integer>());
leaves.get(dOrder-1).add(n.val);
}
return dOrder;
}
}
March 28, 2021 6:15 AM
I found removing leaf nodes in every iteration very intuitive.
I have solved the problem in following way
- do postorder traversal
- add the node to the sublist if it is a leaf node.
- remove the node from the tree if it is a leaf
- add sublist to final answer
It performs in 0ms and memory better than 99.87%.
List> ans = new ArrayList<>();
public List> findLeaves(TreeNode root) {
if(root == null) return ans;
while(true) {
List subAns = new ArrayList();
if(postorder(root, subAns) == 1){
ans.add(subAns);
break;
}
ans.add(subAns);
}
return ans;
}
int postorder(TreeNode root, List subAns) {
if(root == null) return 0;
int left = postorder(root.left, subAns);
int right = postorder(root.right, subAns);
if(root.left == null && root.right == null) {
subAns.add(root.val);
return 1;
}
if(left == 1) {
root.left = null;
}
if(right == 1) {
root.right = null;
}
return 0;
}
}
March 10, 2021 8:12 AM
My O(n) solution using hashMap
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<Integer, List<Integer>> nodeMap = new HashMap<>();
public List<List<Integer>> findLeaves(TreeNode root) {
nodeByHeight(root);
List<List<Integer>> ans = new ArrayList<>();
int key = 0;
while(nodeMap.containsKey(key)) {
ans.add(nodeMap.get(key++));
}
return ans;
}
private int nodeByHeight(TreeNode root) {
if (root == null) return -1;
int left = nodeByHeight(root.left);
int right = nodeByHeight(root.right);
int height = Math.max(left, right) + 1;
List<Integer> arrList = new ArrayList<>();
if (nodeMap.containsKey(height)) {
arrList = nodeMap.get(height);
}
arrList.add(root.val);
nodeMap.put(height, arrList);
return height;
}
}
Last Edit: December 5, 2020 4:30 AM
Am I seriously the first comment?
June 6, 2021 9:42 PM
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
while(!isLeaf(root)) {
List<Integer> picked = new ArrayList();
extractLeaves(root, picked);
res.add(picked);
}
res.add(Collections.singletonList(root.val));
return res;
}
private void extractLeaves(TreeNode root, List<Integer> picked) {
if(!isLeaf(root)) {
if(isLeaf(root.left)) {
// pick root.left
picked.add(root.left.val);
// root.left as null
root.left = null;
}
if(isLeaf(root.right)) {
//
picked.add(root.right.val);
root.right = null;
}
if(root.right != null)
extractLeaves(root.right, picked);
if(root.left != null)
extractLeaves(root.left, picked);
}
}
private boolean isLeaf(TreeNode node) {
if(node != null) {
return node.left == null && node.right == null;
}
return false;
}
}
May 29, 2021 2:22 PM
Why are we returning -1 as the height for leaf nodes? Actually, I tried the same code but I returned 0 as height of leaf node instead of -1. The code failed with the following error: applying non-zero offset 24 to null pointer.
April 22, 2021 11:29 AM
class Solution {
public List<List> findLeaves(TreeNode root) {
List<List<Integer>> output = new ArrayList();
TreeNode tempRoot = root;
while(tempRoot != null && (tempRoot.left != null || tempRoot.right != null)){
List<Integer> leaves = new ArrayList();
collectLeaves(leaves, tempRoot, null, null);
output.add(leaves);
}
List<Integer> rootLevel = new ArrayList();
rootLevel.add(tempRoot.val);
output.add(rootLevel);
return output;
}
public void collectLeaves(List<Integer> leaves, TreeNode root, TreeNode parent, Boolean leftChild){
if(root == null) return;
if(root.left == null && root.right == null){
leaves.add(root.val);
if(parent != null){
if(leftChild){
parent.left = null;
}else{
parent.right = null;
}
}else{
root = null;
}
}else{
collectLeaves(leaves, root.left, root, true);
collectLeaves(leaves, root.right, root, false);
}
}
March 16, 2021 12:11 AM
Swift solution, > 90%
private func find(_ root: TreeNode?, _ ans: inout [[Int]]) -> Int {
if root == nil {return 0}
let h = 1 + max(find(root?.left, &ans), find(root?.right, &ans))
if !ans.indices.contains(h-1) {
let nodes = [Int]()
ans.append(nodes)
}
if let node = root {
ans[h-1].append(node.val)
}
return h
}
func findLeaves(_ root: TreeNode?) -> [[Int]] {
if root == nil {return []}
var ans = [[Int]]()
find(root, &ans)
return ans
}You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: vector<vector<int>> findLeaves(TreeNode* root) { }};